package _2022.hot100._221_最大正方形;

/**
 * @author： YHSimon
 * @date： 2022-05-16 11:23
 */
public class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0, r = matrix.length, c = matrix[0].length;
        int[][] dp = new int[r][c];
        for (int i = 0; i < r; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                maxSide=1;
            }
        }
        for (int i = 0; i < c; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
                maxSide=1;
            }
        }
        for(int i=1;i<r;i++){
            for(int j=1;j<c;j++){
                if(matrix[i][j]=='1'){
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    maxSide=Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide*maxSide;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maximalSquare(new char[][]{
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}
        }));
    }
}
